package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         354,
		Discription: "俄罗斯套娃",
		Level:       3,
		Labels: map[string]int{
			"排序":    1,
			"自定义排序": 1,
			"动态规划":  1,
		},
	})
}

func MaxEnvelopes(envelopes [][]int) int {
	n := len(envelopes)
	fastSort2(envelopes, 0, n-1)
	dp := make([]int, n)
	for i := 0; i < n; i++ {
		dp[i] = 1
	}

	maxCount := 1
	//dp[i]表示以envelopes[0：i+1]的信封的最大套娃数
	for i := 1; i < n; i++ {
		for j := i - 1; j >= 0; j-- {
			if isStrictlySmaller(envelopes[j], envelopes[i]) {
				//排序后如果严格大于某个信封，则在该信封套娃数的基础上+1
				dp[i] = max(dp[i], dp[j]+1)
			}
		}
		if dp[i] > maxCount {
			maxCount = dp[i]
		}
	}

	return maxCount
}

func fastSort2(nums [][]int, start int, end int) {
	if start >= end {
		return
	}

	pivot := partition3(nums, start, end)
	fastSort2(nums, start, pivot)
	fastSort2(nums, pivot+1, end)
}

func partition3(nums [][]int, start int, end int) int {
	i := start
	j := end
	pivot := i
	for i < j {
		for i < j && isSmaller3(nums[pivot], nums[j]) {
			j--
		}
		for i < j && isSmaller3(nums[i], nums[pivot]) {
			i++
		}
		nums[i], nums[j] = nums[j], nums[i]
	}

	nums[i], nums[pivot] = nums[pivot], nums[i]
	return i
}

func isSmaller3(env1 []int, env2 []int) bool {
	//以长为第一判断标准
	if env1[0] < env2[0] {
		return true
	}

	//以宽为第二判断标准
	if env1[0] == env2[0] && env1[1] <= env2[1] {
		return true
	}

	return false
}

func isStrictlySmaller(env1 []int, env2 []int) bool {
	if env1[0] < env2[0] && env1[1] < env2[1] {
		return true
	}

	return false
}
